package Top200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-21 13:48
 * 滑动窗口
 */
public class findSubstring30 {
    public List<Integer> findSubstring(String s, String[] words) {
        int n=s.length();
        int word_len=words[0].length();
        int num=words.length;
        int all_len=word_len*num;
        List<Integer> res=new ArrayList<>();
        HashMap<String,Integer> need=new HashMap<>();
        for (String word:words) {
            need.put(word,need.getOrDefault(word,0)+1);
        }
        int left=0,right=0;
        while (right<n){
            right++;
            if (right-left==all_len) {
                HashMap<String, Integer> windows = new HashMap<>();
                int valid = 0;
                for (int i = left; i < right; i += word_len) {
                    String curword = s.substring(i, i + word_len);
                    if (need.containsKey(curword)) {
                        windows.put(curword, windows.getOrDefault(curword, 0) + 1);
                        if (windows.get(curword).equals(need.get(curword))) {
                            valid++;
                        }
                    } else {
                        break;
                    }
                }
                if (valid == need.size()) {
                    res.add(left);
                }
                left++;
            }else if (right-left<all_len){
                continue;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        findSubstring30 obj=new findSubstring30();
        String s= "barfoothefoobarman";
        String[] words= {"foo", "bar"};
        System.out.println(obj.findSubstring(s,words));
    }
}
